#leetcode题目198：打家劫舍
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：动态规划

from typing import List
class Solution:
    def rob(self, nums: List[int]) -> int:
        """
        打家劫舍
        你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
        影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
        如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
        给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，
        一夜之内能够偷窃到的最高金额。
        """
        n = len(nums)
        
        # 基础情况
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        
        # 初始化dp数组
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[1], nums[0])
        
        # 动态规划循环
        for i in range(2, n):
            # dp[i] 表示到第i个房屋时能偷窃到的最高金额
            # 选择1：偷第i个房屋，那么不能偷第i-1个房屋
            #        总金额 = nums[i] + 到第i-2个房屋的最高金额
            # 选择2：不偷第i个房屋
            #        总金额 = 到第i-1个房屋的最高金额
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        
        return dp[n - 1]



#测试数据
nums = [1,2,3,1] #相邻房间不能同一晚上去偷，否则会触发警报
#预期输出：4
solution = Solution()
print(solution.rob(nums))


nums = [2,7,9,3,1]
#预期输出：12
solution = Solution()
print(solution.rob(nums))